package fun.coding.leetcode;

public class SingleNumberII {

	public static void main(String[] args) {
		SingleNumberII ins = new SingleNumberII();
		int[] test1 = {1, 1, 1, 2, 3, 3, 3};
		System.out.println(ins.singleNumber(test1));
		
		// For negatives, it will append 1 (0 if it is positive) at the left
		// System.out.println(-2 >> 1);
		// For positive, it will append 0 at the right
		// System.out.println(3 << 1);
		
		int[] test2 ={-2,-2,1,1,-3,1,-3,-3,-4,-2};
		System.out.println(ins.singleNumber(test2));
	}
	/*  
	 * This is a neat solution, looping through each bit, and | all the number,
	 * in this case, you don't need to deal with the negative case
    public int singleNumber(int[] A) {
		int result = 0;
        for (int i = 0; i < 32; i++) {
            int count = 0;
            for (int j = 0; j < A.length; j++) {
                count += ((A[j] >> i) & 1); //统计每一位的个数
            }
            result |= ((count % 3) << i);   //取余放回result
        }
    }
	*/
	
	// This method works for 3, 4 ...n numbers are the same, however, there should only be 1 single number different
	public int singleNumber(int[] A) {
		if (A == null) return -1;
		if (A.length == 1) return A[0];
		
		int[] lookup = new int[32];
		
		for (int e : A) {
			// Can't do this while (e > 0) since there will be negatives, and they will be appended by 1
			for (int i = 0; i < 32; i++) {
				if (e == 0) break;
				
				if ((e & 1) == 1) {
					lookup[i] += 1;
				}
				e = e >> 1;
			}
		}
		
		int res = 0;
		for (int i = 0; i < 31; i++) {
			if (lookup[i] % 3 != 0) {
				res += Math.pow(2, i);
			}
		}
		if (lookup[31] % 3 != 0) {
			res = res + Integer.MIN_VALUE;
		}
		
		return res;
	}
	
}
